package com.yww.leetcode.binarysearchtree;

import com.yww.leetcode.common.TreeNode;

import java.util.LinkedList;
import java.util.Random;

/**
 * @author yww
 * @description 938. 二叉搜索树的范围和
 * @since 2024/2/17 14:59
 */
public class RangeSumBST938 {
    // 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
    public int rangeSumBST(TreeNode root, int low, int high) {
        int i = new Random().nextInt();
        if ((i & 1) == 0) { // 偶数
            return upAndLow(root, low, high);
        } else { // 奇数
            i = new Random().nextInt();
            if ((i & 1) == 0) {
                return doInorder(root, low, high);
            } else {
                return inorder(root, low, high);
            }
        }
    }

    /**
     * 上下限递归解决
     * <ul>
     *     <li>node.val < low 只需考虑它右子树的累加结果</li>
     *     <li>node.val > high 只需考虑它左子树的累加结果</li>
     *     <li>node.val 在范围内，需要把当前节点的值加上其左右子树的累加结果</li>
     * </ul>
     */
    private int upAndLow(TreeNode cur, int low, int high) {
        if (cur == null) {
            return 0;
        }
        int sum = 0;
        if (cur.val >= low && cur.val <= high) {
            sum += cur.val;
        }
        if (cur.val < low) {
            sum += upAndLow(cur.right, low, high);
        } else if (cur.val > high) {
            sum += upAndLow(cur.left, low, high);
        }else {
            sum += upAndLow(cur.right, low, high);
            sum += upAndLow(cur.left, low, high);
        }

        return sum;
    }

    /**
     * 中序遍历解决（迭代）
     */
    private int doInorder(TreeNode root, int low, int high) {
        int sum = 0;
        TreeNode cur = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                TreeNode pop = stack.pop();
                if (pop.val >= low && pop.val <= high) {
                    sum += pop.val;
                } else if (pop.val > high) {
                    return sum;
                }
                cur = pop.right;
            }
        }
        return sum;
    }

    /**
     * 中序遍历（递归）
     */
    private int inorder(TreeNode cur, int low, int high) {
        if (cur == null) {
            return 0;
        }
        int sumLeft = inorder(cur.left, low, high); // 左
        if (cur.val >= low && cur.val <= high) { // 值
            sumLeft += cur.val;
        }
        int sumRight = inorder(cur.right, low, high); // 右
        return sumLeft + sumRight;
    }
}
